翻訳と辞書 Words near each other ・ Infinite Possibilities ・ Infinite product ・ Infinite qualitative distinction ・ Infinite regress ・ Infinite Requiem ・ Infinite Rider on the Big Dogma ・ Infinite Ryvius ・ Infinite set ・ Infinite Sorrow ・ Infinite Space ・ Infinite Summer ・ Infinite switch ・ Infinite symmetric product ・ Infinite System ・ Infinite tree ・ Infinite tree automaton ・ Infinite Undiscovery ・ Infinite Visions ・ Infinite Wind Energy ・ Infinite-alleles model ・ Infinite-axis telescope ・ Infinite-dimensional holomorphy ・ Infinite-dimensional Lebesgue measure ・ Infinite-dimensional optimization ・ Infinite-dimensional vector function ・ Infinite-order apeirogonal tiling ・ Infinite-order dodecahedral honeycomb ・ Infinite-order pentagonal tiling ・ Infinite-order square tiling ・ Infinite-order triangular tiling Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Infinite tree automaton ： ウィキペディア英語版 Infinite tree automaton In computer science and mathematical logic, an infinite tree automaton is a state machine that deals with infinite tree structure. It can be viewed as an extension from a finite tree automaton, which accepts only finite tree structures. It can also be viewed as an extension of some infinite word automatons such as the Büchi automaton and the Muller automaton. A finite automaton which runs on an infinite tree was first used by Rabin〔Rabin, M. O.: ''Decidability of second order theories and automata on infinite trees'',''Transactions of the American Mathematical Society'', vol. 141, pp. 1–35, 1969.〕 for proving decidability of monadic second order logic. It has been further observed that tree automaton and logical theories are closely connected and it allows decision problems in logic to be reduced into decision problems for automaton. ==Definition== Infinite tree automaton runs of over a $\backslash Sigma$-labeled tree. There are many slightly different formulations of tree automaton. Here one of the formulation is described. An infinite tree automaton is a tuple $A\; =\; (\backslash Sigma,\; D,\; Q,\; \backslash delta,\; q\_0,\; F\; )$ where, * $\backslash Sigma$ is an alphabet. * $D\backslash subset\; \backslash mathbb$ is a finite set. Each element of $D$ is an allowed degree in input tree. * $Q$ is a finite set of states. * $\backslash delta:\; Q\; \backslash times\; \backslash Sigma\; \backslash times\; D\; \backslash rightarrow\; 2^$ is a transition relation that maps an automaton state $q\; \backslash in\; Q$, an input letter $\backslash sigma\; \backslash in\; \backslash Sigma$, and a degree $d\; \backslash in\; D$ to a set of d-tuple of states. * $q\_0\; \backslash in\; Q$ is an initial state of automaton. * $F\; \backslash subseteq\; \backslash Sigma^$ is an accepting condition. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Infinite tree automaton」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.